The accelerating progress in network speeds and computing power permitted the architectural design paradigm to shift from monolithic applications to microservices. The industry moved from single-core and multi-threads, code-heavy applications, running on giant machines 24/7 to smaller machines, multi-cores single threads where computing power and memory consumption are managed very critically. With the advent of this novel approach to designing systems, traditional multi-tier applications have been broken down into hundreds of microservices that can be easily moved around, start, and stop quickly. In this context, scaling assumed a new meaning, rather than scaling up by adding more resources or computing power, now systems are scaled dynamically by adding more microservices instances. This contribution proposes a theoretical study and a practical experiment to investigate, compare and outline the performance improvements aid by the implementation of Protocol Buffers, Google's language-neutral, binary-based representational data interchange format over traditional text-based serialization formats in a modern, Cloud-Native, REST-based Java Microservice architecture. Findings are presented showing promising results regarding the implementation of Protobuf, with a significant reduction in response time (25.1% faster in the best-case scenario) and smaller payload size (72.28% better in the best-case scenario) when compared to traditional textual serialization formats while literature revealed out-of-the-box mechanisms for message versioning with backward compatibility.