Self-assembly of proteins into complexes with defined stoichiometry and organization is fundamental to the structure and functionality of many molecular machines in biology. Some enteric bacteria including Salmonella have evolved the propanediol-utilizing microcompartment (Pdu MCP), a specialized proteinaceous organelle that is essential for 1,2-propanediol degradation and enteric pathogenesis. Pdu MCPs are a family of bacterial microcompartments that are self-assembled from thousands of protein molecules within the bacterial cytosol. Inside the Pdu MCP, several catalytical enzymes and cofactors involved in reactions for metabolizing 1,2-propanediol are encapsulated in a semi-permeable protein shell that comprises multi-subunit proteins in hexameric, pentameric, and trimeric states. Here, we seek a comprehensive understanding of the stoichiometric composition and organization of Pdu MCPs. We obtain accurate stoichiometry of shell proteins and internal enzymes of the natural Pdu MCP by QconCAT-driven quantitative mass spectrometry. Genetic deletion of the major shell protein and absolute stoichiometry analysis reveal the stoichiometric and structural remodeling of Pdu MCPs. Our new knowledge about the protein stoichiometry leads us to propose a model of the Pdu metabolosome structure. Moreover, atomic force microscopy of Pdu MCPs at the near-physiological condition illustrates the inherent flexibility of the Pdu MCP structure and the key role of cargo enzymes in maintaining mechanical stiffness of the biological architecture. These structural insights into the Pdu MCP will be critical for both delineating the general principles underlying bacterial organelle formation, structural robustness and function, and repurposing natural microcompartments using synthetic biology for biotechnological applications.