The AAA protease FtsH associates with HflK/C subunits to form a megadalton-size complex that spans the inner membrane and extends into the periplasm of E. coli. How this bacterial complex and homologous assemblies in eukaryotic organelles recruit, extract, and degrade membrane-embedded substrates is unclear. Following the overproduction of protein components, recent cryo-EM structures showed symmetric HflK/C cages surrounding FtsH in a manner proposed to inhibit the degradation of membrane-embedded substrates. Here, we present structures of native protein complexes, in which HflK/C instead forms an asymmetric nautilus-shaped assembly with an entryway for membrane-embedded substrates to reach and be engaged by FtsH. Consistent with this nautilus-like structure, proteomic assays suggest that HflK/C enhances FtsH degradation of certain membrane-embedded substrates. Membrane curvature in our FtsH•HflK/C complexes is opposite that of surrounding membrane regions, a property that correlates with lipid scramblase activity and possibly with FtsH's function in the degradation of membrane-embedded proteins.