It's possible to do this entirely in Photoshop, but having a graphics tablet capable of reading stylus tilt and rotation will make this easier. Otherwise, there is plenty of flame stock art you can manipulate and composite.
One way to go about this is to prepare a "fire" gradient going from transparent black, to thin red, on through to orange and yellow, then thinning out again. You can also add white and faint colors such as green or blue (with chemistry determining what color to use). Apply this to a Gradient Fill layer (Layer > New Fill Layer > Gradient) and set it to a mode like Linear Dodge. Pick out a suitable brush, likely a natural media flat brush with reduced flow. Your strokes should resemble ripples on thin, crumpled fabric. Larger strokes should have an upward or wind-following motion.
You may also find pre-made fire brushes useful. To build up the effect, you can use multiple layers, each with a different arrangement of strokes. You may get better results by keeping the size of the flame licks consistent, and varying their scale to suit your basis.