Ifølge skoleordningen af 1844 skulle der oprettes fri- og betalingsskoler for at afhjælpe pladsmangelen i de københavnske skoler. Det var dog uholdbart at gennemføre dette indenfor det gamle sogneinddelingssystem, som derfor blev nedlagt. I stedet blev skolerne inddelt i distrikter.
I 1846 blev der oprettet en friskole og to betalingsskoler. Østre Betalingsskole for børnene i Garnisons og Trinitatis sogne og Vestre Betalingsskole for børnene i Frue, Helliggejst og Holmens sogne, mens friskolen optog elever fra alle sognene. Christianshavn beholdt sine oprindelige skoler.
Vestre Betalingsskole fik til huse i lejede lokaler på Nørregade 41. I 1851 blev opførelsen af en ny skolebygning i Suhmsgade 4 sat i gang. Den blev indviet den 16. august 1852 og taget i brug dagen efter. I 1890 flyttede skolen til Vestervoldgade 98, hvor den blev indviet den 2. september og taget i brug den 10. september. Skolen skiftede navn til Vester Voldgades Betalingsskole.
I 1915 besluttede borgerrepræsentationen, at der ikke mere skulle betales for skolegang, og skolen ændrede navn igen og kom nu til at hedde Vester Voldgades Skole. I 1935 blev skolen lagt sammen med Forchhammersvejs Skole, men blev ved med at hedde Vester Voldgades Skole.
I 1937 blev skolen nedlagt og den Classenske Legatskole overtog lokalerne.