Theo địa chí huyện Thiên Lộc, từ bé Nguyễn Văn Giai rất hứng thú việc học tập và bộc lộ khá rõ một tư chất thông minh. Lên 5 tuổi ông đã biết chữ, 9 tuổi biết làm văn, từng có bài phú: Con trâu trên nghiên mực. Dòng họ ông các đời trước đều thuộc loại khá giả, nhiều người đỗ đạt đại khoa. Nhưng đến đời cụ thân sinh ông Giai là Nguyễn Văn Củng, thì chỉ là khoá sinh và gia thế lâm vào cảnh nghèo túng. Vì vậy, ở tuổi thiếu niên, Nguyễn Văn Giai đã phải tự lao động cày ruộng, bắt cá, làm thuê để giúp đỡ gia đình và kiếm tiền ăn học. Ông có sức vóc hơn người, ăn rất khoẻ và làm lụng thì ít người bì kịp. Giai thoại cho biết Nguyễn Văn Giai có thân hình đẹp, to cao, tiếng nói như chuông đồng, tính tình rất ngay thẳng, hay bênh vực kẻ yếu, đả kích lũ cường hào, nên bị bọn chức sắc ghét bỏ, đuổi khỏi làng. Ông ra Thanh Hóa, đến vùng Đan Nê, huyện Yên Định làm thuê, trọ trong gia đình họ Lê ở gần núi. Năm ấy vào dịp tháng 3, làng tổ chức lễ cúng thần Đồng Cổ, là vị thần Trống Đồng rất linh thiêng, có công giúp vua Hùng Vương và các vua thời Lý - Trần đánh thắng kẻ xâm lược. Hôm đó, xảy ra việc một số mâm cỗ bị mất. Người làng dò xét thấy trong nhà Nguyễn Văn Giai trọ có mâm xôi gà đang ăn dở. Hỏi thì chủ nhà bảo không biết.
