單一的進化樹的數(shù)量會隨著分類群數(shù)量的增長而呈指數(shù)增長，從而變?yōu)橐粋�天文數(shù)字。由于計算能力的限制，現(xiàn)在一般只允許對很小一部分的可能的進化樹進行搜索。具體的數(shù)目主要依賴于分類群的數(shù)量、優(yōu)化標準、參數(shù)設定、數(shù)據(jù)結構、計算機硬件以及計算機軟件。
有兩種搜索方法保證可以找到最優(yōu)化的進化樹：窮舉法和樹枝 跳躍法（BB）。對于一個很大的數(shù)據(jù)集，這兩種方法都很不實用。對分類群數(shù)量的限制主要取決于數(shù)據(jù)結構和計算機速度，但是對于超過20個分類群的數(shù)據(jù)集，BB方法很少會得到應用。窮舉法要根據(jù)優(yōu)化標準，對每一個可能的進化樹進行評估。BB方法提供一個邏輯方法，以確定那些進化樹值得評估，而另一些進化樹可被簡單屏蔽。因此BB方法通常要比窮舉法快得多。
絕大多數(shù)分析方法都使用“啟發(fā)式”的搜索。啟發(fā)式現(xiàn)搜索出相近的次優(yōu)化的進化樹家族（“島嶼”），然后從中得到優(yōu)化解（“山頂”）。不同的算法用不同程度的精確性搜索這些島嶼和山頂。最徹底也是最慢的程序（TBR，tree bisection-reconnection，進化樹對分重接）先把進化樹在每一個內部樹枝處劈開，然后以任意方式將劈開的碎片重新組合起來。最快的算法只是檢查一下相鄰終端的不太重要的重新組合，因此傾向于找到最近的島嶼的山頂。
降低搜索代價的最好方法是對數(shù)據(jù)集進行剪除。影響優(yōu)化搜索策略選擇的因素（數(shù)據(jù)量，數(shù)據(jù)結構，時間量，硬件，分析目的）太復雜，無法推薦一個簡單可行的處方。因此進行搜索的用戶必須對數(shù)據(jù)非常熟悉且有明確的目標，了解各種各樣的搜索程序及自己硬件設備和軟件的能力。
除上述當前應用最廣的方法外，還有大量的建立和搜索進化樹的其它方法。這些方法包括Wagner距離方法和親近方法（距離轉化方法）；Lake的不變式方法（一個基于特征符的方法，它選擇的拓撲結構包含一個意義重大的正數(shù)以支持顛換）；Hadamard結合方法（一個精細的代數(shù)方陣方法，對距離數(shù)據(jù)或者觀察到的特征符進行修正）；裂解方法（這個方法決定在數(shù)據(jù)中應該支持哪一個基于距離的可選的拓撲結構）；四重奏迷惑（Quartet puzzling）方法可以為ML建樹方法所應用，這個算法相對而言是個較快的進化樹搜索算法。