A byte stuffing circuit and a byte stuffing method are provided. The byte stuffing method includes: receiving a first data stream and generating a second data stream according to the first data stream, where a first size of the first data stream is N bytes, and a second size of the second data stream is 2N bytes; in response to an Xth byte of the second data stream matching a first flag byte, overwriting the Xth byte with a first stuffing byte, and inserting a second stuffing byte into an (X+1)th byte of the second data stream, where X is a positive integer between 1 and 2N−1; combining a remnant data stream and a first part of the second data stream to generate a third data stream, and configuring a second part of the second data stream as the remnant data stream; and outputting the third data stream.