To understand physiological processes, insight into protein complexes is very important. Through a combination of blue native gel electrophoresis and LC-MS/MS, we were able to isolate protein complexes and identify their potential subunits from Nicotiana tabacum cv. Bright Yellow-2. For this purpose, a bioanalytical approach was used that works without a priori knowledge of the interacting proteins. Different clustering methods (e.g., k-means and hierarchical clustering) and a biclustering approach were evaluated according to their ability to group proteins by their migration profile and to correlate the proteins to a specific complex. The biclustering approach was identified as a very powerful tool for the exploration of protein complexes of whole cell lysates since it allows for the promiscuous nature of proteins. Furthermore, it searches for associations between proteins that co-occur frequently throughout the BN gel, which increases the confidence of the putative associations between co-migrating proteins. The statistical significance and biological relevance of the profile clusters were verified using functional gene ontology annotation. The proof of concept for identifying protein complexes by our BN PAGE/LC-MS/MS approach is provided through the analysis of known protein complexes. Both well characterized long-lived protein complexes as well as potential temporary sequential multi-enzyme complexes were characterized.