We propose a permutation approach to the classic Behrens-Fisher problem of comparing two means in the presence of unequal variances. It is motivated by the observation that a paired test is valid whether or not the variances are equal. Rather than using a single arbitrary pairing of the data, we average over all possible pairings. We do this in both a parametric and nonparametric setting. When the sample sizes are equal, the parametric version is equivalent to referral of the unpaired t-statistic to a t-table with half the usual degrees of freedom. The derivation provides an interesting representation of the unpaired t-statistic in terms of all possible pairwise t-statistics. The nonparametric version uses the same idea of considering all different pairings of data from the two groups, but applies it to a permutation test setting. Each pairing gives rise to a permutation distribution obtained by relabeling treatment and control within pairs. The totality of different mean differences across all possible pairings and relabelings forms the null distribution upon which the p-value is based. The conservatism of this procedure diminishes as the disparity in variances increases, disappearing completely when the ratio of the smaller to larger variance approaches 0. The nonparametric procedure behaves increasingly like a paired t-test as the sample sizes increase.