Using the ATLAS detector, observations have been made of a centrality-dependent dijet asymmetry in the collisions of lead ions at the Large Hadron Collider. In a sample of lead-lead events with a per-nucleon center of mass energy of 2.76 TeV, selected with a minimum bias trigger, jets are reconstructed in fine-grained, longitudinally-segmented electromagnetic and hadronic calorimeters. The underlying event is measured and subtracted event-by-event, giving estimates of jet transverse energy above the ambient background. The transverse energies of dijets in opposite hemispheres is observed to become systematically more unbalanced with increasing event centrality leading to a large number of events which contain highly asymmetric dijets. This is the first observation of an enhancement of events with such large dijet asymmetries, not observed in proton-proton collisions, and which may point to an interpretation in terms of strong jet energy loss in a hot, dense medium.