1. Start a new image, I used 320x240
2. Set black as your foreground color, white as your background color.
3. Filter > Render > Clouds
4. Filter > Artistic > Fresco (Brush Size - 10, Brush Detail - 10, Texture - 1)
5. Image > Adjustments > Hue/Saturation (Colorize checked, Hue - 0, Saturation - 25, Lightness - -34)
6. Copy the layer.
7. On the copied layer, Image > Adjustments > Hue/Saturation (Colorize checked, Hue - 25, Saturation - 25, Lightness - 0)
8. Set the copied layer's blendind mode to "Linear Dodge"
Now man has made fire

Creator