Two bicyclic carbohydrate-based diols, 2,3:4,5-di-O-methylene-galactitol (Galx) or 2,4:3,5-di-O-methylene-d-mannitol (Manx), were introduced into the backbone of poly(butylene terephthalate) using the solid-state modification technique (SSM). The resulting copolyesters had a unique block-like chemical microstructure that endows them with superior thermal properties when compared with their random counterparts obtained by melt copolymerization. The materials prepared by SSM displayed higher melting points, crystallization temperatures, and crystallinity due to the presence of long PBT sequences in the copolyester. The glass-transition temperatures also increased upon incorporation of the bicyclic comonomers, this effect being more pronounced for Manx units. The melting points of these block-like copolyesters decreased after melting due to the occurrence of randomization, but they remained higher than those of copolyesters prepared from the melt. SSM was demonstrated to be a very suitable technique for the incorporation of rigid monomers into the amorphous phase of PBT, leading to bio-based non-random copolyesters with remarkable thermal properties.