The suitability of municipal plant waste for anaerobic digestion was examined using 57 different herbaceous and non-herbaceous samples. Biochemical methane potential (BMP) and anaerobic biodegradability were related to the degree of lignification and crystallinity of cellulose. The BMP of herbaceous garden plants (332.7 CH4 NL kg VS1) was high, although lower than that of energy crops (400–475 CH4 NL kg VS1). Herbaceous wild plants from natural grassland contained most lignocelluloses, leading to relatively low BMP (214.0 CH4 NL kg VS1). Non-herbaceous phytomass had a high degree of lignification and a high concentration of crystalline cellulose, but due to the content of non-woody parts with a low concentration of lignocellulose the BMP was relatively high, 199.9 and 172.0 CH4 NL kg VS1 for hedge cuttings and woody cuttings, respectively. There were indications that a plant lignin concentration of 100 g kg VS1 is the critical biodegradability point in anaerobic digestion of phytomass.