A growing number of far-infrared bright sources completely invisible in deep extragalactic optical surveys hint at an elusive population of z>4 dusty, star-forming galaxies. Cycle 1 JWST surveys are now detecting their rest-frame optical light, which provides key insight into their stellar properties and statistical constraints on the population as a whole. This work presents the JWST/NIRCam counterpart from the COSMOS-Web survey to a far-infrared SCUBA-2 and ALMA source, AzTECC71, which was previously undetected at wavelengths shorter than 850 microns. AzTECC71, amongst the reddest galaxies in COSMOS-Web with F277W - F444W~0.9, is undetected in NIRCam/F150W and F115W and fainter in F444W than other sub-millimeter galaxies identified in COSMOS-Web by 2-4 magnitudes. This is consistent with the system having both a lower stellar mass and higher redshift than the median dusty, star-forming galaxy. With deep ground- and space-based upper limits combined with detections in F277W, F444W and the far-IR including ALMA Band 6, we find a high probability (99%) that AzTECC71 is at z>4 with z_phot=5.7(+0.8,-0.7). This galaxy is massive (logM*/Msun~10.7) and IR-luminous (logLIR/Lsun~12.7), comparable to other optically-undetected but far-IR bright dusty, star-forming galaxies at z>4. This population of luminous, infrared galaxies at z>4 is largely unconstrained but comprises an important bridge between the most extreme dust-obscured galaxies and more typical high-redshift star-forming galaxies. If further far-IR-selected galaxies that drop out of the F150W filter in COSMOS-Web have redshifts z>4 like AzTECC71, then the volume density of such sources may be ~3-10x greater than previously estimated.