We measure the luminosity profiles of 16 brightest cluster galaxies (BCGs) at $0.4 < z < 0.8$ using high resolution F160W NICMOS and F814W WFPC2 HST imaging. The heterogeneous sample is drawn from a variety of surveys: seven from clusters in the Einstein Medium Sensitivity Survey, five from the Las Campanas Distant Cluster Survey and its northern hemisphere precursor, and the remaining four from traditional optical surveys. We find that the surface brightness profiles of all but three of these BCGs are well described by a standard de Vaucouleurs ($r^{1/4}$) profile out to at least $sim2r_{e}$ and that the biweight-estimated NICMOS effective radius of our high redshift BCGs ($r_{e} = 8.3pm 1.4$ kpc for $H_{0} = 80$ km s$^{-1}$ Mpc$^{-1}$, $Omega_{m} = 0.2, Omega_Lambda = 0.0$) is $sim 2$ times smaller than that measured for a local BCG sample. If high redshift BCGs are in dynamical equilibrium and satisfy the same scaling relations as low redshift ones, this change in size would correspond to a mass growth of a factor of 2 since $z sim 0.5$. However, the biweight-estimated WFPC2 effective radius of our sample is 18 $pm $ 5.1 kpc, which is fully consistent with the local sample. While we can rule out mass accretion rates higher than a factor of 2 in our sample, the discrepancy between our NICMOS and WFPC2 results, which after various tests we describe appears to be physical, does not yet allow us to place strong constraints on accretion rates below that level.