单一的进化树的数量会随着分类群数量的增长而呈指数增长，从而变为一个天文数字。由于计算能力的限制，现在一般只允许对很小一部分的可能的进化树进行搜索。具体的数目主要依赖于分类群的数量、优化标准、参数设定、数据结构、计算机硬件以及计算机软件。
有两种搜索方法保证可以找到最优化的进化树：穷举法和树枝 跳跃法（BB）。对于一个很大的数据集，这两种方法都很不实用。对分类群数量的限制主要取决于数据结构和计算机速度，但是对于超过20个分类群的数据集，BB方法很少会得到应用。穷举法要根据优化标准，对每一个可能的进化树进行评估。BB方法提供一个逻辑方法，以确定那些进化树值得评估，而另一些进化树可被简单屏蔽。因此BB方法通常要比穷举法快得多。
绝大多数分析方法都使用“启发式”的搜索。启发式现搜索出相近的次优化的进化树家族（“岛屿”），然后从中得到优化解（“山顶”）。不同的算法用不同程度的精确性搜索这些岛屿和山顶。最彻底也是最慢的程序（TBR，tree bisection-reconnection，进化树对分重接）先把进化树在每一个内部树枝处劈开，然后以任意方式将劈开的碎片重新组合起来。最快的算法只是检查一下相邻终端的不太重要的重新组合，因此倾向于找到最近的岛屿的山顶。
降低搜索代价的最好方法是对数据集进行剪除。影响优化搜索策略选择的因素（数据量，数据结构，时间量，硬件，分析目的）太复杂，无法推荐一个简单可行的处方。因此进行搜索的用户必须对数据非常熟悉且有明确的目标，了解各种各样的搜索程序及自己硬件设备和软件的能力。
除上述当前应用最广的方法外，还有大量的建立和搜索进化树的其它方法。这些方法包括Wagner距离方法和亲近方法（距离转化方法）；Lake的不变式方法（一个基于特征符的方法，它选择的拓扑结构包含一个意义重大的正数以支持颠换）；Hadamard结合方法（一个精细的代数方阵方法，对距离数据或者观察到的特征符进行修正）；裂解方法（这个方法决定在数据中应该支持哪一个基于距离的可选的拓扑结构）；四重奏迷惑（Quartet puzzling）方法可以为ML建树方法所应用，这个算法相对而言是个较快的进化树搜索算法。