A methodology is proposed to solve a difficult modeling problem related to the recently sequenced P39 protein. This sequence shares no similarity with any known 3D structure, but a fold is proposed by several threading tools. The difficulty in aligning the target sequence on one of the proposed template structures is overcome by combining the results of several available prediction methods and by refining a rational consensus between them. In silico validation of the obtained model and a preliminary cross-check with experimental features allow us to state that this borderline prediction is at least reasonable. This model raises relevant hypotheses on the main structural features of the protein and allows the design of site-directed mutations. Knowing the genetic context of the P39 reading frame, we are now able to suggest a function for the P39 protein: it would act as a periplasmic substrate-binding protein.