ARABIDILLO proteins are F-box-Armadillo (ARM) proteins that regulate root branching in Arabidopsis. Many F-box proteins in plants, yeast and mammals are unstable. In plants, the mechanism for this instability has not been fully investigated. Here, we show that a conserved family of plant ARABIDILLO-related proteins has a unique domain structure consisting of an F-box and leucine-rich repeats (LRRs) followed by ARM-repeats. The LRRs are similar to those found in other plant and animal F-box proteins, including cell cycle proteins and hormone receptors. We demonstrate that the LRRs are required for ARABIDILLO1 function in vivo. ARABIDILLO1 protein is unstable: we show that ARABIDILLO1 protein is associated with ubiquitin and is turned over by the proteasome. Both the F-box and LRR regions of ARABIDILLO1 appear to enable this turnover to occur. Application of known lateral root-regulating signals has no effect on ARABIDILLO1 stability. In addition, plants that lack or overexpress ARABIDILLO proteins respond normally to known lateral root-regulating signals. Thus, we suggest that the signal(s) regulating ARABIDILLO stability in vivo may be either highly specific or novel. The structural conservation between ARABIDILLOs and other plant and animal F-box proteins suggests that the stability of other F-box proteins may be controlled by similar mechanisms.