Traditional major depressive disorder (MDD) interventions do not improve heart rate variability (HRV), despite symptom reduction. We investigated whether respiratory sinus arrhythmia (RSA)-biofeedback (BFB) effectively changed HRV, psychological symptoms, and functional connectivity of the default mode network (DMN), which is known to increase in MDD. Thirty MDD patients were randomly assigned to two groups (RSA-BFB with treatment as usual [TAU] with medication [BFB + TAU; n = 16] and TAU [n = 14]). Six RSA-BFB sessions were performed over 4 weeks. We assessed psychological symptoms (including depression, anxiety, and hopelessness), high frequency (HF; an index of HRV during rest and stress), and DMN functional connectivity, as measured by source-level coherence of 19-channel electroencephalography using standardized weighted low-resolution brain electromagnetic tomography. Large-scale DMN was represented by small-worldness based on graph theory. The BFB + TAU group showed greater reductions in depression (especially psychic anxiety and vegetative symptoms) compared to the TAU group. Significant group by session interactions were found in resting HF-HRV, stress-reactive HF-HRV, and beta DMN small-worldness. During the post-intervention session, the BFB + TAU group showed higher resting HF-HRV and stress-reactive HF-HRV (d = 1.41 for the resting stage and d = 1.99 for the Stroop test, P < .005). Compared to baseline, the BFB + TAU group showed increased HF-HRV reactivity and decreased DMN small-worldness in the beta band, implying decreased global DMN functional connectivity. Conversely, the TAU group showed decreased HF-HRV during stress and no DMN alterations. This study was limited by small sample size and open-label design. These preliminary findings suggest that brief RSA-BFB may improve autonomic nervous system and DMN functions in MDD.