A video transcoding method and device, and a storage medium are disclosed in embodiments of the present disclosure. The method includes the following steps: obtaining a video sequence in source video data, and obtaining a source video frame in the video sequence, the source video data including a plurality of video sequences arranged in a sequence arrangement order; obtaining a first ratio of a sum of absolute transformed differences of an initial frame in the video sequence to a bit rate of the video sequence, and adjusting a quantization parameter of the source video frame based on the first ratio; encoding the source video frame based on an adjusted quantization parameter to obtain a target video frame, and replacing the source video frame with the target video frame to obtain a video sequence after the replacement; and adding the video sequence after the replacement to target video data according to the sequence arrangement order.