Light-weight high pressure vessels are recently in demand mainly because of the need to replace gasoline engines with hydrogen fuel cells. One of the main problems delaying this transition is our inability to store sufficient hydrogen in automobiles without (1) sacrificing safety and cabin space and (2) achieving the same driving range and performance as gasoline-powered vehicles. While hydrogen is more efficient as a fuel than gasoline and has zero greenhouse gas emissions, it occupies a larger volume and violently explodes in contact with air. Thus, hydrogen tanks are significantly larger and heavier than those of gasoline. Storage of compressed fluids has always relied on round tanks because of their high membrane resistance and low surface-to-volume ratios. Multilayered composite and metal designs are then used to reinforce and reduce their weight. Apparently, the best idea-but still early in its development-is to store hydrogen based on metal hydrides. Nevertheless, we present a new concept of replacing conventional hydrogen tanks with tanks that are internally reinforced by space-filling skeletons or simply with strut/shell networks. This enables designs of lighter, stronger tanks with shapes that can fit into nonfunctional regions of the vehicle to significantly increase storage volume. This approach promises immediate integration with existing storage technologies. Treating the reinforced vessel as joined plates on elastic foundations, we analyze cylindrical and rectangular tanks and show that the idea is more efficient in terms of pressure gain and weight reduction in the latter because large wall deformations favor the skeleton reinforcement. This result validates the skeleton reinforcement idea, and its practicality is discussed.