Paksujalka syntyi luovutettuihin alueisiin kuuluvassa Hiitolan kunnassa vuonna 1883. Hänen vanhempansa olivat maanviljelijä Jaakko Paksujalka ja Maria Karvonen. Juho Paksujalka oli itsekin varsinaiselta ammatiltaan maanviljelijä ja työskenteli Hiitolassa, Artjärvellä sekä Anjalassa. Hän oli vuodesta 1905 naimisissa Hilma Maria Sinkkosen kanssa.