We consider the randomized decision tree complexity of the recursive 3‐majority function. We prove a lower bound of (1/2−δ)·2.57143h for the two‐sided‐error randomized decision tree complexity of evaluating height h formulae with error δ∈[0,1/2) . This improves the lower bound of (1−2δ)(7/3)h given by Jayram, Kumar, and Sivakumar (STOC'03), and the one of (1−2δ)·2.55h given by Leonardos (ICALP'13). Second, we improve the upper bound by giving a new zero‐error randomized decision tree algorithm that has complexity at most (1.007)·2.64944h . The previous best known algorithm achieved complexity (1.004)·2.65622h . The new lower bound follows from a better analysis of the base case of the recursion of Jayram et al. The new algorithm uses a novel “interleaving” of two recursive algorithms. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 612–638, 2016