The notion of proximal normal structure is introduced and used to study mappings that are "relatively nonexpansive" in the sense that they are defined on the union of two subsets A and B of a Banach space X and satisfy ∥ Tx-Ty∥ ≤ ∥ x-y∥ for all x ∈ A, y ∈ B. It is shown that if A and B are weakly compact and convex, and if the pair (A,B) has proximal normal structure, then a relatively nonexpansive mapping T: A ∪ B → A ∪ B satisfying (i) T(A) ⊆ B and T(B) ⊆ A, has a proximal point in the sense that there exists x₀ ∈ A ∪ B such that ∥ x₀-Tx₀∥ = dist(A,B). If in addition the norm of X is strictly convex, and if (i) is replaced with (i)' T(A) ⊆ A and T(B) ⊆ B, then the conclusion is that there exist x₀ ∈ A and y₀ ∈ B such that x₀ and y₀ are fixed points of T and ∥ x₀ -y₀∥ = dist(A,B). Because every bounded closed convex pair in a uniformly convex Banach space has proximal normal structure, these results hold in all uniformly convex spaces. A Krasnosel'skiĭ type iteration method for approximating the fixed points of relatively nonexpansive mappings is also given, and some related Hilbert space results are discussed.