Yes, but they were aided by a series of fortuitous (well, for some people) circumstances.

When Cortéz first landed on the Yucatan they encountered a spanish prisoner (from an earlier expedition) who had lived among the Maya for many years and was fluent in mayan. This meant Cortéz had access to a language known in the area (so they could always find a nahuatl-to-maya translator and then translate nahuatl-to-maya-to-spanish)

They used this later on when Cortéz was given a group of slave-women by a local maya ruler, one of which, Malintzin, was a presumably highborn woman who spoke nahautl. So Cortéz then had access to a chain of translators that could speak with the aztec rulers.

There's always room for discussion, but perhaps the section Cross-cultural communication and lingua francas from our FAQ will answer your inquiry.